package danran.bfs;

import java.util.*;

/**
 * @Classname MinMutation
 * @Description TODO
 * @Date 2021/9/21 15:02
 * @Created by ASUS
 */
public class MinMutation {

    char[] base = new char[]{'A', 'G', 'C', 'T'};

    public int minMutation(String start, String end, String[] bank) {
        Set<String> set = new HashSet<>(Arrays.asList(bank));
        if (!set.contains(end)) return -1;
        int step = 0;
        Queue<String> q = new ArrayDeque<>();
        q.offer(start);
        while (!q.isEmpty()) {
            int size = q.size();
            System.out.println(q);
            step++;
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                assert cur != null;
                if (cur.equals(end)) return step;
                for (int index = 0; index < cur.length(); index++) {
                    for (char c : base) {
                        if (cur.charAt(index) != c) {
                            StringBuilder builder = new StringBuilder(cur);
                            builder.setCharAt(index, c);
                            if (set.contains(builder.toString())) {
                                if (builder.toString().equals(end)) return step;
                                q.offer(builder.toString());
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String start = "AAAAACCC";
        String end = "AACCCCCC";
        String[] blank = new String[]{"AAAACCCC", "AAACCCCC", "AACCCCCC"};
        System.out.println(new MinMutation().minMutation(start, end, blank));
    }
}
